package compile.lesson4;

import java.util.*;

/**
 * 表示文法产生式的类，包括产生式左部符号和右部符号列表的组合。
 */
class Production {
    String lhs;//左部
    List<String> rhs;//右部符号列表

    public Production(String lhs, List<String> rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(lhs);
        sb.append(" -> ");
        for (String symbol : rhs) {
            sb.append(symbol);
            sb.append(" ");
        }
        return sb.toString();
    }
}


/**
 * 表示 LR(0) 项的类，由一个文法产生式和一个符号位置组成。
 */
class LR0Item {
    Production production;//对应的文法产生式
    int dotPosition;//符号位置，即 "." 所在的位置。取值范围为 [0, production.rhs.size()]。

    public LR0Item(Production production, int dotPosition) {
        this.production = production;
        this.dotPosition = dotPosition;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        LR0Item other = (LR0Item) obj;
        return dotPosition == other.dotPosition && Objects.equals(production, other.production);
    }

    @Override
    public int hashCode() {
        return Objects.hash(production, dotPosition);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append(production.lhs);
        sb.append(" ->");

        for (int i = 0; i < production.rhs.size(); i++) {
            if (i == dotPosition) {
                sb.append(" .");
            }
            sb.append(" ");
            sb.append(production.rhs.get(i));
        }

        if (dotPosition == production.rhs.size()) {
            sb.append(" .");
        }

        return sb.toString();
    }
}
/**
 * 表示 LR(0) 自动机中的状态。一个状态由多个 LR(0) 项组成，并且具有一个唯一的 index。
 */
class LR0State {
    List<LR0Item> items;//该状态中包含的 LR(0) 项列表。
    int index;//该状态在自动机中的唯一编号。

    public LR0State(List<LR0Item> items,int index) {
        this.items = items;
        this.index= index;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        LR0State other = (LR0State) obj;
        return Objects.equals(new HashSet<>(items), new HashSet<>(other.items));
    }

    @Override
    public int hashCode() {
        return Objects.hash(new HashSet<>(items));
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(":");
        for (LR0Item item : items) {
            sb.append("\n\t").append(item.toString());
        }
        return sb.toString();
    }
}

public class LR0Parser_3 {
    Map<String, List<Production>> grammar;//保存文法
    List<LR0State> states;//保存LR0的项目集，一个项目集就是一个状态
    Map<LR0State, Map<String, LR0State>> transitions;

    Map<Integer, Map<String, String>> goToTable;
    Map<Integer, Map<String, String>> actionTable;

    public LR0Parser_3(Map<String, List<Production>> grammar) {
        this.grammar = grammar;
        this.states = new ArrayList<>();
        this.transitions = new HashMap<>();
        this.actionTable = new HashMap<>();
        this.goToTable = new HashMap<>();
        //调用自动机构建项目集
        buildAutomaton();
    }
    /**
     * 返回文法中使用的所有符号（终结符和非终结符）的集合。
     * @return 文法中使用的所有符号
     */
    private Set<String> allSymbols() {
        Set<String> symbols = new HashSet<>();
        for (List<Production> productions : grammar.values()) {
            for (Production production : productions) {
                symbols.addAll(production.rhs);
            }
        }
        //把文法中不再产生式右部的符号也加进去 即左部的非终结符
        symbols.addAll(grammar.keySet());
        return symbols;
    }

    /**
     * 计算给定 LR(0) 状态的闭包。
     * @param state 要计算闭包的 LR(0) 状态
     * @return 该状态中包含的所有 LR(0) 项的闭包
     * 一个LR0
     */
    private LR0State closure(LR0State state) {
        Set<LR0Item> closureItems = new HashSet<>(state.items);
        boolean changed;

        do {
            changed = false;
            Set<LR0Item> newItems = new HashSet<>();

            for (LR0Item item : closureItems) {
                if (item.dotPosition < item.production.rhs.size()) {
                    String symbol = item.production.rhs.get(item.dotPosition);

                    if (grammar.containsKey(symbol)) {
                        for (Production production : grammar.get(symbol)) {
                            LR0Item newItem = new LR0Item(production, 0);

                            //如果项不在原状态中，就把它加入新项集中
                            if (!closureItems.contains(newItem)) {
                                newItems.add(newItem);
                                changed = true;
                            }
                        }
                    }
                }
            }

            closureItems.addAll(newItems);
        } while (changed);

        return new LR0State(new ArrayList<>(closureItems), state.items.size()+1);
    }

    /**
     * 计算通过将 LR(0) 状态中的点向前移动一个位置，并附加给定符号的结果 LR(0) 状态。
     * @param state 要进行转移的 LR(0) 状态
     * @param symbol 要附加到新状态的符号
     * @return 在给定状态下附加给定符号后获得的 LR(0) 状态
     */
    private LR0State goTo(LR0State state, String symbol) {
        Set<LR0Item> nextStateItems = new HashSet<>();

        for (LR0Item item : state.items) {//{[S'->.E],[E->.xxT]}遍历项目集中的每一个项目
            //item.production.rhs.get(item.dotPosition).equals(symbol)后面这一段啥意思呢？
            //例如当前item为S'->.E , symbol为E 那么点右移一位（吃进一位）的符号正好和symbol相等
            if (item.dotPosition < item.production.rhs.size() && item.production.rhs.get(item.dotPosition).equals(symbol)) {
                // 满足上述条件，就将项中的点向右移动一个位置，并生成新的项，即由 S'->.E 生成新的项 S' -> E.
                nextStateItems.add(new LR0Item(item.production, item.dotPosition + 1));
            }
        }
        // 计算新状态的闭包
        return closure(new LR0State(new ArrayList<>(nextStateItems),state.items.size()+1));
    }

    /**
     * 构建 LR(0) 自动机（项集族）。
     */
    private void buildAutomaton() {
        Set<LR0State> stateSet = new HashSet<>();//用来保存项目集，保证唯一性，不重复添加
        Queue<LR0State> queue = new LinkedList<>();//队列，广度优先遍历
        // 创建初始状态（闭包） 以S'->.E项目为初始项目构建初始项目集（初始状态）
        // 调用求闭包，其实就是找等价类，找到的一个闭包就是一个状态，也叫一个项目集
        LR0State startState = closure(new LR0State(Arrays.asList(new LR0Item(grammar.get("S'").get(0), 0)),0));
        stateSet.add(startState);//将这个项目集添加到set中
        queue.add(startState);

        while (!queue.isEmpty()) {
            LR0State currentState = queue.poll();

            for (String symbol : allSymbols()) {//allSymbols()返回文法中使用的所有符号（终结符和非终结符）的集合。遍历每一个符号，看当前状态集是否能通过该符号转移到下一个状态
                // 对于文法中的每个符号，计算通过在当前状态上进行转移附加该符号的下一个状态
                LR0State nextState = goTo(currentState, symbol);//如{[S'->.E],[E->.xxT]}状态通过T啥也到不了，nextState为空

                if (!nextState.items.isEmpty() && stateSet.add(nextState)) {
                    // 如果新状态不为空并且不属于已存在的状态集合，就将其加入队列和状态集合中
                    queue.add(nextState);
                }

                if (!nextState.items.isEmpty()) {
                    // 在转移表中添加从当前状态到下一个状态的映射,将从当前状态 currentState 向符号 symbol 可转移到的下一个状态 nextState 加入到 transitions 中
                    // 如{[S'->.E],[E->.xxT]}  可以通过 S 到达 {[S'->E.]}，由此可以找到所有的状态（项目集），并且我通过transitions记录了状态间的转换关系
                    // 根据这个transitions可以求得构造表
                    transitions.computeIfAbsent(currentState, k -> new HashMap<>()).put(symbol, nextState);
                }
            }
        }
        // 将状态集合转换成状态列表
        states = new ArrayList<>(stateSet);
    }

    /**
     * 根据映射关系构造Action表和Goto表
     * 1.构造Action表和Goto表，其行数为项目集集合的个数，列数分别是终结符和非终结符的数量
     * 2.遍历每一个项集，填充表
     *      a.
     *
     */

    /**
     * 构造Goto表，遍历非终结符
     */
    private void buildGotoTable() {
        for (LR0State itemSet : states) {//状态集
            goToTable.put(itemSet.index, new HashMap<>());
            for (String symbol : grammar.keySet()) {//遍历非终结符
                //找到映射关系
                //例如1 [S' -> . S, S -> . x x T] 吃入了 符号 S 到达的下一个状态 就是要goto的状态
                Map<String,LR0State> map=transitions.get(itemSet);
                if(map!=null){
                    LR0State gotoLR0State=map.get(symbol);
                    if (gotoLR0State!=null&&!"S'".equals(symbol)) {
                        int goToItemSetId = gotoLR0State.index;
                        goToTable.get(itemSet.index).put(symbol, "goto"+goToItemSetId);
                    }
                }

            }
        }
    }

    /**
     * 编写人：黎旭
     * 构造Action表，遍历终结符以及结束符号
     */
    private void buildActionTable() {
        for (LR0State itemSet : states) {
            actionTable.put(itemSet.index, new HashMap<>());
            for (String terminal : new String[]{"x", "y","$"}) {//遍历非终结符以及结束符号
                LR0State goToItemSet = goTo(itemSet, terminal);
                if (goToItemSet != null) {
                    int goToItemSetId = goToItemSet.index;
                    actionTable.get(itemSet.index).put(terminal, "s" + goToItemSetId);
                }
            }
            for (LR0Item item : itemSet.items) {
                if (item.dotPosition == item.production.rhs.size()) {//如果点在文法的最后
                    //并且找到S'->S·，则置Action[k,$]为acc，表示接受
                    if (item.production.lhs.equals("S'")) {
                        actionTable.get(itemSet.index).put("$", "accept");
                    //如果点在文法的最后，那么就把Action[k,`]的每一项置为rj
                    } else {
                        for (String terminal : new String[]{"x", "y","$"}) {
//                            actionTable.get(itemSet.index).put(terminal, "r {" + item.production.lhs + " -> " + String.join(" ", item.production.rhs+"}"));
                            if(itemSet.index==3) {
                                actionTable.get(itemSet.index).put(terminal, "r0");
                            }else{
                                actionTable.get(itemSet.index).put(terminal,"r2");
                            }
                        }

                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<String, List<Production>> grammar = new HashMap<>();
        /**
         * 构造文法
         * 非终结符 S E T
         * 产生式
         *      S'->s
         *      S->xxT
         *      T->y
         */
        grammar.put("S'", Collections.singletonList(new Production("S'", Arrays.asList("S"))));
        grammar.put("S", Arrays.asList(
                new Production("S", Arrays.asList("x", "x","T"))
        ));
        grammar.put("T", Collections.singletonList(new Production("T", Arrays.asList("y"))));

        /**
         *
         */
        LR0Parser_3 parser = new LR0Parser_3(grammar);

        //打印求得的所有状态集合，每一个集合就是一个状态
        System.out.println("States:");
        for(int i=0;i<parser.states.size();++i){
            LR0State state = parser.states.get(i);
            state.index=i;
            System.out.println(state.index+" "+state.items.toString());
        }


        //打印状态集合的之间的转换关系，其实这里就是一个DFA，或者说是一个状态转换图
        System.out.println("\nTransitions:");
        for (Map.Entry<LR0State, Map<String, LR0State>> entry : parser.transitions.entrySet()) {
            System.out.println(entry.getKey().items.toString() + " -> \n" + entry.getValue());
        }

        parser.buildActionTable();
        parser.buildGotoTable();

        System.out.println("LR0 Action构造表");
        for(Map.Entry<Integer,Map<String,String>> entry:parser.actionTable.entrySet()){
            System.out.println(entry.getKey()+" -> "+entry.getValue());
        }

        System.out.println("\nLR0 Goto构造表");
        for(Map.Entry<Integer,Map<String,String>> entry:parser.goToTable.entrySet()){
            System.out.println(entry.getKey()+" -> "+entry.getValue());

        }
    }
}
